package 力扣_树算法.二叉树;

import java.util.Deque;
import java.util.LinkedList;

/**101.对称二叉树
 * @author zx
 * @create 2022-04-10 12:29
 */
public class Num101 {
    public boolean isSymmetric2(TreeNode root) {
            //借助队列：使用层序遍历
            //判断左右两颗树是否轴对称
            //左树的左要和右树的右节点值相同
            //左树的右要和右树的左节点值相同
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root.left);
        queue.offer(root.right);
        while(!queue.isEmpty()){
            //一次性取出两个节点,这两个节点就是两颗子树的根节点
            //一次判断一组元素(两个)
            TreeNode t1 = queue.poll();
            TreeNode t2 = queue.poll();
            if(t1 == null && t2 == null){
                continue;
            }
            if(t1 == null || t2 == null){
                return false;
            }
            if(t1.val != t2.val){
                return false;
            }
            //左右两颗树都不为空且根节点的节点值相同，继续判断t1.left和t2.right以及t1.right和t2.left
            queue.offer(t1.left);
            queue.offer(t2.right);
            //入队另一组元素
            queue.offer(t1.right);
            queue.offer(t2.left);
        }
        return true;
    }

    /**
     * @return 递归
     */
    public boolean isSymmetric(TreeNode root) {
        //递归拆分子问题：左树的值等于右树的值 && root.left.left == root.right.right && root.left.right == root.right.left
        if(root == null){
            return true;
        }
        return isMirror(root.left,root.right);
    }
    private boolean isMirror(TreeNode left,TreeNode right){
        if(left == null && right == null){
            return true;
        }
        if(left == null || right == null){
            return false;
        }
        if(left.val != right.val){
            return false;
        }
        return isMirror(left.left,right.right) && isMirror(left.right,right.left);
    }
}
